<!DOCTYPE html>
<html lang="en">

<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Lazy Code Motion Optimizer Framework</title>
<link rel="stylesheet" type="text/css" href="https://gcc.gnu.org/gcc.css" />
</head>

<body>
<h1>Lazy Code Motion Optimizer Framework</h1>

<p>March 10, 1999</p>

<p>We are pleased to announce that Cygnus has donated a lazy code motion
optimizer framework (LCM).</p>

<p>LCM is a general technique for performing global optimizations such
as <a href="gcse.html">global cse and partial redundancy elimination</a>.</p>

<p>LCM is an improvement over other global redundancy elimination algorithms
because it can typically find more redundancies and minimize register lifetimes.
In fact, in a 100% complete implementation LCM can be shown to be
computationally optimal.</p>

<p>The LCM algorithm Cygnus has donated is based on the lazy code motion
algorithms found in Steven Muchnick's book, Advanced Compiler Design and
Implementation (pages 407-415).  LCM optimizers are provided which work
on both the forward and the reverse flow graphs.</p>

<p> The basic concept behind LCM is to initially move all expressions as
far up in the flowgraph as possible.  This exposes the maximum number of
redundancies.  Then expressions are then pushed as far down in the flow
graph as possible, which minimizes register lifetimes.</p>

<p>This implementation is missing one key feature which prevents it from
being computationally optimal, specifically critical edge splitting.  While the
optimizer works and will perform better than most global optimizers, the
lack of critical edge splitting prevents the resulting code from being
computationally optimal.</p>

<p>We will be shortly reworking the global cse optimizer to use the lazy
code motion framework.  We expect other optimizations using the lazy code
motion framework to be added to the compiler in the future.  For example,
the lazy code motion framework can be used to implement spill code motion.</p>

</body>
</html>
